#pragma once

#include "dfa.hpp"
#include "nfa_interpretor.hpp"
#include <iostream>
#include <vector>
#include "nfa_machine_constructor.hpp"

namespace dfa
{
    const int STATE_FAILURE = -1;
    const uint8_t ASCII_COUNT = 128;
    const uint32_t MAX_DFA_STATE_COUNT = 256;

    class DfaConstructor
    {
    public:
        DfaConstructor (nfa::NfaPair* nfa_pair_p, nfa::Nmc* nfa_machine_p)
            : _nfa_pair_p(nfa_pair_p)
            , _nfa_machine_p(nfa_machine_p)
            , _nfa_interpretor_p(new nfa::NfaInterpretor()) 
        { initTransTable(_dfa_state_trans_table); }

        auto convertNfaToDfa()
        {
            std::unordered_set<nfa::Nfa*> input;
            input.insert(_nfa_pair_p->_start);
            auto nfa_start = _nfa_interpretor_p->epsilonClousre(input);
            auto start = Dfa::getDfaFromNfaSet(nfa_start);
            _dfa_list.push_back(start);
            _dfa_set.insert(start);
            auto next_state = STATE_FAILURE;
            for (size_t i = 0; i < _dfa_list.size(); ++i) {
                auto cur_dfa = _dfa_list[i];
                for (uint8_t c = 0; c < ASCII_COUNT; ++c) {
                    auto move = _nfa_interpretor_p->move(cur_dfa->getNfaStates(), c);
                    if (move.empty()) next_state = STATE_FAILURE;
                    else {
                        auto closure = _nfa_interpretor_p->epsilonClousre(move);
                        auto dfa_new = Dfa::getDfaFromNfaSet(closure);
                        auto dfa_exist = dfaExists(dfa_new);
                        if (dfa_exist) {
                            Dfa::dfaFree(dfa_new);
                            next_state = dfa_exist->getStateNum();
#ifdef DEBUG_SHOW
                            std::cout << "cur_dfa: " << cur_dfa->getStateNum() << " accept: " << (char)c << " -> " << next_state << " contains nfa state: " << cur_dfa->showNfaStates() << " state: " << cur_dfa->getAccepted() << std::endl;
#endif
                        } else {
                            _dfa_list.push_back(dfa_new);
                            _dfa_set.insert(dfa_new);
                            next_state = dfa_new->getStateNum();
#ifdef DEBUG_SHOW
                            std::cout << "cur_dfa: " << cur_dfa->getStateNum() << " accept: " << (char)c << " -> " << next_state << " contains nfa state: " << cur_dfa->showNfaStates() << " state: " << cur_dfa->getAccepted() << std::endl;
#endif
                        }
                    }
                    _dfa_state_trans_table[cur_dfa->getStateNum()][c] = next_state;
                }
            }
            return _dfa_state_trans_table;
        }

        auto getDfaTransTable()
        { return _dfa_state_trans_table; }

        std::vector<Dfa*>& getDfaList()
        { return _dfa_list; }

        ~DfaConstructor()
        { for (const auto& e : _dfa_list) delete e; }

        static void initTransTable(std::vector<std::vector<int>>& trans_table)
        {
            auto value = STATE_FAILURE;
            std::vector<std::vector<int>> temp(MAX_DFA_STATE_COUNT, std::vector<int>(ASCII_COUNT, value));
            trans_table.swap(temp);
        }

        static void printDfaTable(std::vector<std::vector<int>>& dfa_trans_table)
        {
            for (size_t i = 0; i < dfa_trans_table.size(); ++i) 
                for (size_t j = 0; j < dfa_trans_table[i].size(); ++j) 
                    if (isOnNumClass(i, j, dfa_trans_table)) 
                        std::cout << "from " << i << " to " << j << " on D" << std::endl;
                    else if (isOnDot(i, j, dfa_trans_table)) 
                        std::cout << "from " << i << " to " << j << " on ." << std::endl;
        }

    private:
        struct dfaHasher {
            std::size_t operator()(Dfa* dfa) const 
            {
                std::vector<size_t> nfa_state_nums;
                auto nfa_states = dfa->getNfaStates();
                for (const auto& e : nfa_states) nfa_state_nums.push_back(e->getNum());
                sort(nfa_state_nums.begin(), nfa_state_nums.end());
                auto hash_code = nfa_state_nums[0];
                for(int i = 1; i < nfa_state_nums.size(); ++i) hash_code = (hash_code * HASH_FACTOR + nfa_state_nums[i]) % MOD;
                return hash_code;
            }
        };

        struct dfaEqual {
            bool operator()(Dfa* dfa1, Dfa* dfa2) const 
            { return dfaHasher{}(dfa1) == dfaHasher{}(dfa2); }
        };

        Dfa* dfaExists(Dfa* dfa) const
        {
            auto res = _dfa_set.find(dfa);
            return res == _dfa_set.end() ? nullptr : *res;
        }

        static bool isOnNumClass(int from, int to, std::vector<std::vector<int>>& trans_table)
        {
            for (char c = '0'; c < '0' + 9; ++c) 
                if (trans_table[from][c] == to) return true;
            return false;
        }

        static bool isOnDot(int from, int to, std::vector<std::vector<int>>& trans_table)
        { return trans_table[from]['.'] == to ? true : false; }

        const static uint32_t HASH_FACTOR = 31;
        const static uint32_t MOD = 1000000007;
        std::vector<std::vector<int>> _dfa_state_trans_table;
        std::vector<dfa::Dfa*> _dfa_list;
        std::unordered_set<dfa::Dfa*, dfaHasher, dfaEqual> _dfa_set;
        nfa::Nmc* _nfa_machine_p;
        nfa::NfaInterpretor* _nfa_interpretor_p;
        nfa::NfaPair* _nfa_pair_p;
    };
}
